SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Problème algorithmique</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Problème algorithmique</span></h1>

</header>

</div>

<p>Un <b>problème algorithmique</b> est, en <a href="Informatique_th%C3%A9orique" title="Informatique théorique">informatique théorique</a>, un objet <a href="Math%C3%A9matiques" title="Mathématiques">mathématique</a> qui représente une question ou un ensemble de questions auxquelles un <a href="Ordinateur" title="Ordinateur">ordinateur</a> devrait être en mesure de répondre. Le plus souvent, ces problèmes sont de la forme : étant donné un objet (l'instance), effectuer une certaine action ou répondre à telle question.

</p><p>Par exemple, le problème de la <a href="Factorisation" title="Factorisation">factorisation</a> est le problème suivant : étant donné un nombre entier, trouver un <a href="Facteur_premier" class="mw-redirect" title="Facteur premier">facteur premier</a> de cet entier.

</p><p>On distingue en particulier trois types de problèmes<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> :

</p>

<ul><li>les <a href="Probl%C3%A8me_de_d%C3%A9cision" title="Problème de décision">problèmes de décision</a>, qui consistent à répondre oui ou non à une question (par exemple, cet entier est-il premier ?) ;</li>

<li>les <a href="Probl%C3%A8me_%C3%A0_promesse" title="Problème à promesse">problèmes à promesse</a>, qui consistent à répondre oui ou non à une question uniquement sous une hypothèse (la promesse) ;</li>

<li>les <a href="Probl%C3%A8me_de_recherche" title="Problème de recherche">problèmes de recherche</a> et les problèmes de fonction, qui consistent à produire un objet spécifié par l'énoncé du problème (par exemple, la factorisation). La différence réside dans le fait que les problèmes de fonction ont exactement une solution correspondant à chaque instance.</li></ul>

<p>Les problèmes algorithmiques jouent un rôle central en <a href="Informatique_th%C3%A9orique" title="Informatique théorique">informatique théorique</a> et forment un domaine à part entière, à côté de celui des <a href="Algorithme" title="Algorithme">algorithmes</a> qui étudient les méthodes efficaces de résolution de problèmes décidables et de celui de l'<a href="Analyse_de_la_complexit%C3%A9_des_algorithmes" title="Analyse de la complexité des algorithmes">analyse de la complexité des algorithmes</a> qui cherche à comprendre les performances de ces algorithmes.

</p>

<div class="mw-heading mw-heading2"><h2 id="Vocabulaire">Vocabulaire</h2></div>

<p>Un problème algorithmique est le plus souvent formulé par un ensemble d'<i>entrées</i> possibles, appelées <i>instances</i>, et des contraintes sur la sortie. L'algorithme doit pouvoir calculer, à partir de l'instance, une sortie qui satisfait les contraintes en question.

</p><p>En d'autres termes, une instance est un ensemble de données d'entrée qui satisfont les contraintes imposées par l'énoncé d'un problème algorithmique.

</p>

<div class="mw-heading mw-heading2"><h2 id="Classification_par_difficulté"><span id="Classification_par_difficult.C3.A9"></span>Classification par difficulté</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Décidabilité"><span id="D.C3.A9cidabilit.C3.A9"></span>Décidabilité</h3></div>

<p>Un problème peut être <a href="D%C3%A9cidabilit%C3%A9" title="Décidabilité">décidable</a> ou indécidable. Un problème est décidable s'il existe un algorithme pour le résoudre.

</p>

<div class="mw-heading mw-heading3"><h3 id="Complexité"><span id="Complexit.C3.A9"></span>Complexité</h3></div>

<p>Une fois la décidabilité démontrée, une deuxième question se pose, concernant l'efficience de la recherche d'une solution. Dans ce cas il faut fixer une représentation des données et des solutions du problème pour pouvoir dire quelque chose sur la <a href="Complexit%C3%A9_g%C3%A9n%C3%A9rique_des_algorithmes" title="Complexité générique des algorithmes">complexité</a>. Il y a deux cas.

</p>

<div class="mw-heading mw-heading4"><h4 id="Nombre_d'opérations"><span id="Nombre_d.27op.C3.A9rations"></span>Nombre d'opérations</h4></div>

<p>Une possibilité (mais il y en a d'autres<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>) est de postuler que les instances et les solutions sont représentées par un tableau binaire (contenant donc uniquement des éléments de {0, 1}<sup>*</sup>). Par exemple, les nombres sont représentés de <a href="Syst%C3%A8me_binaire" title="Système binaire">façon binaire</a>, les graphes sont codés de façon binaire ainsi que les <a href="Machine_de_Turing" title="Machine de Turing">machines de Turing</a>. Dans la suite, nous nous concentrerons sur cette façon d'exprimer la complexité et nous identifierons les nombres, les graphes, les machines, etc. à leur représentation binaire.

</p>

<div class="mw-heading mw-heading4"><h4 id="Nombre_de_solutions">Nombre de solutions</h4></div>

<p>Dans ce cas, il s'agit de compter le nombre de solutions ou plus précisément le nombre de <a href="Certificat_(complexit%C3%A9)" title="Certificat (complexité)">certificats</a>. La principale complexité dans ce cas est la complexité <a href="#P">#P</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Taxonomie_des_problèmes_algorithmiques"><span id="Taxonomie_des_probl.C3.A8mes_algorithmiques"></span>Taxonomie des problèmes algorithmiques</h2></div>

<p>Un <a href="Probl%C3%A8me_de_d%C3%A9cision" title="Problème de décision">problème de décision</a> est un problème où la réponse de chaque instance est soit « oui », soit « non ». Ainsi le <a href="Test_de_primalit%C3%A9" title="Test de primalité">test de primalité</a> d'un nombre entier est un problème algorithmique :

</p>

<dl><dd>« Soit un nombre entier naturel, <i>n</i>, déterminer si <i>n</i> est <a href="Nombre_premier" title="Nombre premier">premier</a>. »</dd></dl>

<p>Un problème de décision est souvent assimilé à l'ensemble des instances pour lesquelles la réponse est « oui ». Dans l'exemple précédent, le problème de primalité est assimilé à l'ensemble des nombres premiers :

</p>

<p>Dans un <a href="Probl%C3%A8me_de_recherche" title="Problème de recherche">problème de recherche</a>, la réponse est un élément associé à l'élément d'entrée par la relation qui apparaît dans l'énoncé du problème. Par exemple, le problème de factorisation ci-dessus cherche des solutions dont la donnée est un nombre et le résultat est un couple de nombres dont la première composante est un nombre premier et le produit des composantes est le nombre donné dans l'énoncé.

</p><p>Un problème de recherche est donné par une <a href="Relation_(math%C3%A9matiques)" title="Relation (mathématiques)">relation binaire</a> appelée <i>relation de recherche</i>. Par exemple, la factorisation est la relation

</p>

<p>qui comprend toutes les paires de nombres (<i>n</i>, <i>p</i>), où <i>p</i> est un facteur premier non trivial de <i>n</i><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>.

</p><p>Un problème de dénombrement vise à déterminer le nombre de solutions d'un problème de recherche donné. Par exemple, le problème de dénombrement associé à celui de la factorisation est

</p>

<dl><dd>« Soit un entier <i>n</i>, déterminer le nombre de facteurs premiers non triviaux de <i>n</i>. »</dd></dl>

<p>Un problème de dénombrement a pour résultat un entier naturel. Pour chaque relation de recherche <i>R</i>, le problème de dénombrement associé à <i>R</i> est une fonction

</p>

<p>Un problème d'optimisation cherche une solution « meilleure » que les autres parmi toutes les solutions possibles d'un problème de recherche. On peut citer comme exemple, la recherche du plus grand facteur premier d'un nombre.

</p><p>Un problème d'optimisation contient dans son énoncé sa relation de recherche à laquelle on ajoute la contrainte de trouver une solution optimale.

</p><p>Dans un problème de fonction, un seul résultat au plus est attendu pour chaque entrée, mais sa nature est plus complexe que celle d'un <a href="Probl%C3%A8me_de_d%C3%A9cision" title="Problème de décision">problème de décision</a> puisque le résultat est une valeur et non pas « oui » ou « non » comme dans un problème de décision.

</p>

<div class="mw-heading mw-heading2"><h2 id="Notes_et_références"><span id="Notes_et_r.C3.A9f.C3.A9rences"></span>Notes et références</h2></div>

<ul><li><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé <span class="">« <a class="external text" href="https://en.wikipedia.org/wiki/Computational_problem?oldid=664751158">Computational problem</a> » <small>(<a class="external text" href="https://en.wikipedia.org/wiki/Computational_problem?action=history">voir la liste des auteurs</a>)</small></span>.</li></ul>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a> </span><span class="reference-text"><span class="ouvrage" id="Perifel14">Sylvain <span class="nom_auteur">Perifel</span>, <cite class="italique">Complexité algorithmique</cite>, <a href="%C3%89ditions_Ellipses" title="Éditions Ellipses">Ellipses</a>, <time>2014</time>, 432 <abbr class="abbr" title="pages">p.</abbr> <small style="line-height:1em;">(<a href="International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <span class="nowrap">9782729886929</span>, <a rel="nofollow" class="external text" href="http://www.liafa.univ-paris-diderot.fr/~sperifel/livre_complexite.html">lire en ligne</a>)</small>, <abbr class="abbr" title="chapitre(s)">chap.</abbr> 1 (« Le modèle de calcul »)<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Complexit%C3%A9+algorithmique&rft.atitle=Le+mod%C3%A8le+de+calcul&rft.pub=Ellipses&rft.aulast=Perifel&rft.aufirst=Sylvain&rft.date=2014&rft.tpages=432&rft.isbn=9782729886929&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AProbl%C3%A8me+algorithmique"></span></span>.</span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><a href="#cite_ref-2">↑</a> </span><span class="reference-text">Par exemple, on peut imaginer une représentation des nombres en bâtons ou une présentation des nombres en virgule flottante.</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><a href="#cite_ref-3">↑</a> </span><span class="reference-text">La « relation » d'un problème peut ne peut pas être calculable, auquel cas l'énumération comme dans la relation ci-dessus n'existe pas.</span>

</li>

</ol></div>

<ul id="bandeau-portail" class="bandeau-portail"><li><span class="bandeau-portail-element"><span class="bandeau-portail-icone"><span class="noviewer skin-invert-image" typeof="mw:File"></span></span> <span class="bandeau-portail-texte">Portail de l'informatique théorique</span> </span></li> </ul></div><div><div class="zim-footer">

Cet article est issu de <a class="external text" title="Dernière modification le 2025-03-19" href="https://fr.wikipedia.org/wiki/?title=Probl%C3%A8me_algorithmique&oldid=224035216">Wikipédia</a>. Sauf mention contraire, le texte est disponible sous <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.fr">Creative Commons Attribution-Share Alike 4.0</a>. Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.

</div>

</div></div>

</div>

</main>

</div>

</body></html>